The valuations of the near hexagons related to the Witt designs S(5,6,12) and S(5,8,24)

Valuations of dense near polygons were introduced in 16 . In the present paper, we classify all valuations of the near hexagons ??₁ and ??₂, which are related to the respective Witt designs S(5,6,12) and S(5,8,24). Using these classifications, we prove that if a dense near polygon S contains a hex H isomorphic to ??₁ or ??₂, then H is classical in S. We will use this result to determine all dense near octagons that contain a hex isomorphic to ??₁ or ??₂. As a by‐product, we obtain a purely geometrical proof for the nonexistence of regular near 2d‐gons, d ≥ 4, whose parameters s, t, t_i (0 ≤ i ≤ d) satisfy (s, t₂, t₃) = (2, 1, 11) or (2, 2, 14). The nonexistence of these regular near polygons can also be shown with the aid of eigenvalue techniques. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 214–228, 2006     

关于半无爪图点泛圈性的两个结果

给出了半无爪图(quasi-claw-freegraph)点泛圈性方面的两个结果,作为推论,可得到D.Oberly,D.Sumner,L.Clark等人的相关结果.     

正整数的一类三分拆的应用

利用正整数n的一类特殊的3分拆n=n1+n2+n3,n1>n2>n3≥1,且n2+n3>n1的Ferrers图将不定方程4x1+3x2+2x3=n(n≥9)的正整数解与这种分拆联系起来,从而得到了该不定方程的正整数解数公式;同时也给出了正整数n的一类4分拆的计数公式.此外,还给出了周长为n的整边三角形的计数公式的一个简单证明.     

On disjoint configurations in infinite graphs

For a graph A and a positive integer n, let nA denote the union of n disjoint copies of A; similarly, the union of ?₀ disjoint copies of A is referred to as ?₀A. It is shown that there exist (connected) graphs A and G such that nA is a minor of G for all n??, but ?₀A is not a minor of G. This supplements previous examples showing that analogous statements are true if, instead of minors, isomorphic embeddings or topological minors are considered. The construction of A and G is based on the fact that there exist (infinite) graphs G₁, G₂,… such that G_i is not a minor of G_j for all i ≠ j. In contrast to previous examples concerning isomorphic embeddings and topological minors, the graphs A and G presented here are not locally finite. The following conjecture is suggested: for each locally finite connected graph A and each graph G, if nA is a minor of G for all n ? ?, then ?₀A is a minor of G, too. If true, this would be a far‐reaching generalization of a classical result of R. Halin on families of disjoint one‐way infinite paths in graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 222–229, 2002; DOI 10.1002/jgt.10016     

On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.     

LA RECONSTRUCTION DES TOURNOIS SANS DIAMANT

We prove that if T is a tournament of order n > 6 in which any 4-sub-tournament is hamiltonian or transitive, then T is reconstructible in the sense of Ulam.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

完全二部图Ka,b的迭线图L^m（Ka，b）的谱特征

本证明了当(a，b)不属于{(1，8)，(2，4)，(3，6)，(4，4)，(2s^2-s，2s^2 s))时，L^m(Ka,b)以谱为特征，其中a≤b，s≥2．     

(a,b,n)-临界图的几个充分条件

设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 .     

Large families of mutually embeddable vertex‐transitive graphs

For each infinite cardinal κ, we give examples of 2^κ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all graphs with smaller orders as induced subgraphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 99–106, 2003